Clustering Obstacles

You have a way to segment points and recognize which ones represent obstacles for your car. It would be great to break up and group those obstacle points, especially if you want to do multiple object tracking with cars, pedestrians, and bicyclists, for instance. One way to do that grouping and cluster point cloud data is called euclidean clustering.

Euclidean Clustering

The idea is you associate groups of points by how close together they are. To do a nearest neighbor search efficiently, you use a KD-Tree data structure which, on average, speeds up your look up time from O(n) to O(log(n)). This is because the tree allows you to better break up your search space. By grouping points into regions in a KD-Tree, you can avoid calculating distance for possibly thousands of points just because you know they are not even considered in a close enough region.

In this lesson, you will begin by seeing how to do Euclidean clustering using built-in PCL functions. Next, you will write your own clustering algorithm using a KD-Tree. Your implementation will be used in your project submission, so be sure to complete the implementation in the exercises that follow!